package com.up.interview.dataStructuresAndAlgorithms;

/**
 * @author: liuchengjun
 * @title: dynamicProgramming
 * @projectName: 海联技术中台V2.0
 * @depart 软件事业部
 * @description:
 * @date: 2025/10/23/周四 16:45 (星期四)
 * @since V2.0
 */
public class DynamicProgramming {


    /**
     * F(0) = 0  F(1) = 1   F(n) = F(n-1) + F(n-2) （当 n ≥ 2）
     * @param n
     * @return  问题：重复求解子问题
     */
    public int f(int n){
        if(n==0){
            return 0 ;
        }
        if(n==1){
            return 1 ;
        }
        return f(n-1)+f(n-2);
    }

    public int test(int n){
        int[] arr = new int[n];
        arr[1] = 1;
        return f2(n,arr);
    }

    public int f2(int n,int[] arr){
        if(n ==0 || arr[n] != 0){
            return arr[n];
        }
        int i = f(n - 1) + f(n - 2);
        arr[n] = i;
        return i;
    }

    //一层维度：记录子问题的解，通过子问题的解求解问题的解
    public int f3(int n){
        if(n<=1){
            return n;
        }
        int[] dp = new int[n];
        dp[1] = 1;
        for (int i = 2; i < n+1; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n-1];
    }
}
